package dataspace

type node struct {
	hash        uint64   // хеш ключа
	key, value  []byte   // ключ-значение
	element     *element // элемент списка
	left, right *node    // указатели на ноды
	height      int      // ширина
}

// Метод ищет ноду по ключу.
func (n *node) search(h uint64) *node {
	if n == nil {
		return nil
	}
	switch {
	case h < n.hash:
		return n.left.search(h)
	case h == n.hash:
		return n
	case h > n.hash:
		return n.right.search(h)
	}
	return nil
}

// Метод записывает ноду в дерево.
func (n *node) add(h uint64, k, v []byte, e *element) *node {
	if n == nil {
		return &node{
			hash:    h,
			key:     k,
			value:   v,
			element: e,
			left:    nil,
			right:   nil,
			height:  1,
		}
	}
	switch {
	case h < n.hash:
		n.left = n.left.add(h, k, v, e)
	case h == n.hash:
		n = &node{
			hash:    h,
			key:     k,
			value:   v,
			element: e,
			left:    n.left,
			right:   n.right,
			height:  n.height,
		}
	case h > n.hash:
		n.right = n.right.add(h, k, v, e)

	}
	return n.rebalance()
}

// Метод удаляет ноду из дерева.
func (n *node) remove(h uint64) *node {
	if n == nil {
		return nil
	}
	switch {
	case h < n.hash:
		n.left = n.left.remove(h)
	case h == n.hash:
		switch {
		case n.left != nil && n.right != nil:
			r := n.right.findMinimalNode()
			n = &node{
				hash:    r.hash,
				key:     r.key,
				value:   r.value,
				element: r.element,
				left:    n.left,
				right:   n.right.remove(r.hash),
				height:  n.height,
			}
		case n.left != nil:
			n = n.left
		case n.right != nil:
			n = n.right
		default:
			return nil
		}
	case h > n.hash:
		n.right = n.right.remove(h)
	}
	return n.rebalance()
}

// Метод ищет минимальную ноду в ветке.
func (n *node) findMinimalNode() *node {
	if n.left == nil {
		return n
	}
	return n.left.findMinimalNode()
}

// Метод получает ширину ветви.
func (n *node) getHeight() int {
	if n == nil {
		return 0
	}
	return n.height
}

// Метод устанавливает ширину ноды.
func (n *node) setHeight() {
	n.height = 1 + max(n.left.getHeight(), n.right.getHeight())
}

// Метод поворачивает дерево влево.
func (n *node) rotateLeft() *node {
	r := n.right
	n.right = r.left
	r.left = n
	n.setHeight()
	r.setHeight()
	return r
}

// Метод поворачивает дерево вправо.
func (n *node) rotateRight() *node {
	l := n.left
	n.left = l.right
	l.right = n
	n.setHeight()
	l.setHeight()
	return l
}

// Метод балансирует дерево.
func (n *node) rebalance() *node {
	if n == nil {
		return nil
	}
	n.setHeight()
	switch n.left.getHeight() - n.right.getHeight() {
	case -2:
		if n.right.left.getHeight() > n.right.right.getHeight() {
			n.right = n.right.rotateRight()
		}
		return n.rotateLeft()
	case 2:
		if n.left.right.getHeight() > n.left.left.getHeight() {
			n.left = n.left.rotateLeft()
		}
		return n.rotateRight()
	}
	return n
}
